Conventionally, navigation devices that search for a route based on map data and provide guidance on the route are known. For example, in Japanese Patent Application; Publication No. JP-A-2008-241474, if a vehicle has deviated a guided route, a route is searched based on travel histories such that roads that are often included in the travel histories are used by priority.